package demo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-26
 * Time: 19:56
 */
public class TestDemo1 {


    //象棋跳马问题
    public static int jump1(int x,int y,int k){
        return process(0,0,x,y,k);
    }

    public static int process(int a,int b,int x,int y,int rest){
        if(x<0||x>9||y<0||y>8){
            return 0;
        }
        if(rest==0){
            return x==a&&y==b ? 1 : 0;
        }
        int ways = process(a,b,x+2,y+1,rest-1);
        ways += process(a,b,x+1,y+2,rest-1);
        ways += process(a,b,x-1,y+2,rest-1);
        ways += process(a,b,x-2,y+1,rest-1);
        ways += process(a,b,x-2,y-1,rest-1);
        ways += process(a,b,x-1,y-2,rest-1);
        ways += process(a,b,x+1,y-2,rest-1);
        ways += process(a,b,x+2,y-1,rest-1);
        return ways;
    }

    public static int jump2(int a,int b,int k){
        int[][][] dp = new int[10][9][k+1];
        dp[a][b][0] = 1;
        for(int rest =1 ;rest<=k;++rest){
            for(int x = 0;x<10;++x){
                for(int y =0;y<9;++y){
                    int ways = pick(dp,x+2,y+1,rest-1);
                    ways +=  pick(dp,x+1,y+2,rest-1);
                    ways +=  pick(dp,x-1,y+2,rest-1);
                    ways +=  pick(dp,x-2,y+1,rest-1);
                    ways +=  pick(dp,x-2,y-1,rest-1);
                    ways +=  pick(dp,x-1,y-2,rest-1);
                    ways +=  pick(dp,x+1,y-2,rest-1);
                    ways +=  pick(dp,x+2,y-1,rest-1);
                    dp[x][y][rest] = ways;
                }
            }
        }
        return dp[0][0][k];
    }

    public static int pick(int[][][] dp,int x,int y,int k){
        if(x<0||x>9||y<0||y>8){
            return 0;
        }
        return dp[x][y][k];
    }

    public static void main(String[] args) {
        System.out.println(jump1(7, 7, 10));
        System.out.println(jump2(7, 7, 10));
    }


}
